Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Розрахункова робота
З теорії алгоритмів
Варіант №5
Завдання:
Знайдіть у цьому лабіринті такий маршрут, щоб сума всіх “зібраних” на перехрестях чисел дорівнювала 40. Через кожне перехрестя можна проходити лише один раз.
Алгоритм:
Створюємо копію початкового масиву, з якою і будемо працювати
Перевіряємо чи сума цифр більша ніж задана.
Якщо більша, то завершуємо програму (щлях вибрано не правильно)
Якщо менше, то додаємо поточний елемент і відмічаємо пройдений елемент.
Перевіряємо чи поточна клітинка є останньою і сума така як задана
Якщо так, то виводимо увесь відмічений шлях і завершуємо програму.
Якщо ні, то переходимо до іншого перехрестя і йдемо на крок 2
Текст програми:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
#define MAXX 5
#define MAXY 7
#define STARTX 3
#define STARTY 1
#define FINX 0
#define FINY 5
#define FINSUM 40
// тут зберігається граф
int aa[MAXX][MAXY] = {
// 0 1 2 3 4 5 6
/*0*/ {-1,-1, 6, 4, 0, 0,-1},
/*1*/ {-1, 1, 9, 0, 6, 9,-1},
/*2*/ { 3, 6, 4, 2, 5, 3, 0},
/*3*/ {-2, 7, 8, 1, 0, 7,-1},
/*4*/ {-1,-1, 0, 6, 3,-1,-1}};
// вивід графа
void show_matrix(int a[MAXX][MAXY]) {
for(int x=0;x<MAXX;x++)
for(int y=0;y<MAXY;y++) {
printf( "%2d ", a[x][y] );
if(y==MAXY-1) printf( "\n" );
}
}
// рекурсивна функція обходу масива
void array_walk(int x, int y, int sum, int a[MAXX][MAXY]) {
// клонумо масив у newa
int newa[MAXX][MAXY];
memcpy(newa, a, sizeof(newa));
// якщо сума вже більша за потрібну, рухатись далі нема змісту
if(sum>FINSUM) return;
sum+=newa[x][y]; // додаємо до суми поточне значення
newa[x][y]=-2; // відмічаємо пройдену клітинку
// якщо остання клітинка
if((sum==FINSUM)&&(x==FINX)&&(y==FINY)) {
printf("\n Sum: %d \n", sum);
printf(" Way: \n");
// вивід кінцевої матриці із шляхом, відміченим '-2'
show_matrix(a);
return;
}
// визначення можливих клітинок та рух по них
if((x<MAXX-1)&&(a[x+1][y]>=0)) array_walk(x+1,y,sum,newa);
if((y<MAXY-1)&&(a[x][y+1]>=0)) array_walk(x,y+1,sum,newa);
if((x>0)&&(a[x-1][y]>=0)) array_walk(x-1,y,sum,newa);
if((y>0)&&(a[x][y-1]>=0)) array_walk(x,y-1,sum,newa);
}
int main(void)
{
setlocale(LC_ALL, "Ukrainian");
printf( "\n Input:\n" );
show_matrix(aa);
printf( "\n Press Enter...\n" );
getchar();
array_walk(STARTX,STARTY,0,aa);
getchar();
return 0;
}
/
/
